# 675 困难：为高尔夫比赛砍树
# from queue import PriorityQueue
#
#
# def cutOffTree(forest):
#     sortForest = sorted([forest[i][j] for i in range(len(forest))
#                          for j in range(len(forest[0])) if forest[i][j] > 0])
#
#     ret = len(sortForest) - 1
#
#     vis = [[False] * len(forest[0]) for _ in range(len(forest))]
#     vis[0][0] = True
#
#     q = PriorityQueue()
#     q.put((1, 0, 0))
#
#     move = [[0, -1], [0, 1], [1, 0], [-1, 0]]
#
#     # 找到起始点
#     def begin():
#         while not q.empty():
#             _, i, j = q.get()
#             for t in range(4):
#                 x, y = i + move[t][0], j + move[t][1]
#                 if 0 <= x < len(forest) and 0 <= y < len(forest[0]):
#                     if not vis[x][y] and forest[x][y] > 0:
#                         if forest[x][y] == sortForest[0]:
#                             return x, y
#                         q.put((1, x, y))
#                         vis[x][y] = True
#         return -1, -1
#
#     ii, jj = begin()
#     if ii == -1:
#         return -1
#     else:
#         q = PriorityQueue()
#         q.put((sortForest[0], ii, jj))
#         vis = [[False] * len(forest[0]) for _ in range(len(forest))]
#         vis[ii][jj] = True
#
#     def bfs():
#         while not q.empty():
#             _, i, j = q.get()
#             print(_, i, j)
#             if forest[i][j] != sortForest[0]:
#                 return -1
#             else:
#                 sortForest.pop(0)
#
#             for t in range(4):
#                 x, y = i + move[t][0], j + move[t][1]
#                 if 0 <= x < len(forest) and 0 <= y < len(forest[0]):
#                     if not vis[x][y] and forest[x][y] > 0:
#                         q.put((forest[x][y], x, y))
#                         vis[x][y] = True
#
#             print(sortForest, q.qsize())
#
#     bfs()
#
#     return -1 if len(sortForest) > 0 else ret


# print(cutOffTree([[1, 2, 3], [0, 0, 0], [7, 6, 5]]))
# print(cutOffTree([[2, 3, 4], [0, 0, 5], [8, 7, 6]]))
# print(cutOffTree([[1, 2, 3], [0, 0, 4], [7, 6, 5]]))
# print(cutOffTree([[54581641, 64080174, 24346381, 69107959],
#                   [86374198, 61363882, 68783324, 79706116],
#                   [  668150, 92178815, 89819108, 94701471],
#                   [83920491, 22724204, 46281641, 47531096],
#                   [89078499, 18904913, 25462145, 60813308]]))


class Solution:

    def cutOffTree(self, forest: List[List[int]]) -> int:
        def bfs(sx: int, sy: int, tx: int, ty: int) -> int:
            m, n = len(forest), len(forest[0])
            q = deque([(0, sx, sy)])
            vis = {(sx, sy)}
            while q:
                d, x, y = q.popleft()
                if x == tx and y == ty:
                    return d
                for nx, ny in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):
                    if 0 <= nx < m and 0 <= ny < n and forest[nx][ny] and (nx, ny) not in vis:
                        vis.add((nx, ny))
                        q.append((d + 1, nx, ny))
            return -1

        trees = sorted((h, i, j) for i, row in enumerate(forest) for j, h in enumerate(row) if h > 1)
        ans = preI = preJ = 0
        for _, i, j in trees:
            d = bfs(preI, preJ, i, j)
            if d < 0:
                return -1
            ans += d
            preI, preJ = i, j
        return ans
